//A robot is located at the top-left corner of a m x n grid (marked 'Start' in t
//he diagram below). 
//
// The robot can only move either down or right at any point in time. The robot 
//is trying to reach the bottom-right corner of the grid (marked 'Finish' in the d
//iagram below). 
//
// How many possible unique paths are there? 
//
// 
// Example 1: 
//
// 
//Input: m = 3, n = 7
//Output: 28
// 
//
// Example 2: 
//
// 
//Input: m = 3, n = 2
//Output: 3
//Explanation:
//From the top-left corner, there are a total of 3 ways to reach the bottom-righ
//t corner:
//1. Right -> Down -> Down
//2. Down -> Down -> Right
//3. Down -> Right -> Down
// 
//
// Example 3: 
//
// 
//Input: m = 7, n = 3
//Output: 28
// 
//
// Example 4: 
//
// 
//Input: m = 3, n = 3
//Output: 6
// 
//
// 
// Constraints: 
//
// 
// 1 <= m, n <= 100 
// It's guaranteed that the answer will be less than or equal to 2 * 109. 
// 
// Related Topics 数组 动态规划 
// 👍 991 👎 0


package leetcode.editor.cn;

//Java：Unique Paths
class P62UniquePaths {
    public static void main(String[] args) {
        Solution solution = new P62UniquePaths().new Solution();
        System.out.println(solution.uniquePaths(7, 3));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;
        int[][] memo;

        public int uniquePaths(int m, int n) {
            int[][] matrix = new int[m][n];
            return path(0, 0, matrix);

        }


        public int uniquePathsCu(int m, int n) {
            int[][] matrix = new int[m][n];
            return pathC(0, 0, matrix);

        }

        public int uniquePathsC(int m, int n) {
            int[][] matrix = new int[m][n];
            pathR(0, 0, matrix);
            memo = new int[m][n];
            return count;
        }

        //1.自顶向下迭代
        private int path(int x, int y, int[][] matrix) {
            memo = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < memo.length; i++) {
                memo[i][0] = 1;
            }
            for (int j = 0; j < memo[0].length; j++) {
                memo[0][j] = 1;
            }
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    memo[i][j] = memo[i - 1][j] + memo[i][j - 1];

                }
            }
            return memo[matrix.length - 1][matrix[0].length - 1];
        }

        //2.剪枝
        private int pathC(int x, int y, int[][] matrix) {
            if (x == 1 && y == 1) {
                return 1;
            }
            if (isInArea(x, y, matrix) && memo[x][y] == 0) {
                memo[x][y] = pathC(x - 1, y, matrix) + pathC(x, y - 1, matrix);
            }
            return memo[matrix.length - 1][matrix[0].length - 1];
        }

        //3.递归
        private void pathR(int x, int y, int[][] matrix) {

            if (x == matrix.length - 1 && y == matrix[0].length - 1) {
                count++;
                return;
            }
            if (isInArea(x + 1, y, matrix)) {
                pathR(x + 1, y, matrix);
            }
            if (isInArea(x, y + 1, matrix)) {
                pathR(x, y + 1, matrix);
            }
        }

        public boolean isInArea(int x, int y, int[][] matrix) {
            if (x >= matrix.length) {
                return false;
            }
            if (y >= matrix[0].length) {
                return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}